//dp[i][j]表示字符串1[0, i]和字符串2[0, j]范围内的最长公共子序列
//如果s1[i] == s2[j]，那么此时的最长公共子序列一定是以这个相等的字符结尾的
    //dp[i][j] == dp[i - 1][j - 1] + 1
//如果s1[i] != s2[j]，那么此时的最长公共子序列
    //可能由s1[i - 1], s2[j]结尾，即dp[i - 1][j]
    //可能由s1[j], s2[j - 1]结尾，即dp[i][j - 1]
    //可能由s1[i - 1], s2[j - 1]结尾，即dp[i - 1][j - 1]
    //前面两种情况包含了第三种情况，因此只考虑1，2情况即可
class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<short>> dp(m + 1, vector<short>(n + 1, 0));
        s1 = "|" + s1;
        s2 = "_" + s2;

        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                if (s1[i] == s2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
};